package com.lun.swordtowardoffer2.c15;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class LongestConsecutive {

	public int longestConsecutive(int[] nums) {
		Set<Integer> set = new HashSet<>();
		
		for(int num : nums) {
			set.add(num);
		}
		
		int longest = 0;
		
//		for(int num : set) {
//			longest = Math.max(longest, bfs(set, num));
//		}//会抛出ConcurrentModificationException
		
		while(!set.isEmpty()) {
			Iterator<Integer> iter = set.iterator();
			longest = Math.max(longest, bfs(set, iter.next()));
		}
		
		return longest;
	}

	private int bfs(Set<Integer> set, int num) {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.offer(num);
		set.remove(num);
		int length = 1;
		
		while(!queue.isEmpty()) {
			int i = queue.poll();
			int[] neighbors = new int[] {i - 1, i + 1};
			for(int neighbor : neighbors) {
				if(set.contains(neighbor)) {
					set.remove(neighbor);
					queue.offer(neighbor);
					length++;
				}
			}
		}
		return length;
	}
	
	public int longestConsecutive2(int[] nums) {
		Map<Integer, Integer> fathers = new HashMap<>();//son's id to father's id
		Map<Integer, Integer> counts = new HashMap<>();//id to the num of son
//		Set<Integer> all = new HashSet<>();
		
		for(int num : nums) {
			fathers.put(num, num);
			counts.put(num, 1);
//			all.add(num);
		}
		
		for(int num : nums) {
			if(counts.containsKey(num + 1)) {
				union(fathers, counts, num, num + 1);
			}
			if(counts.containsKey(num - 1)) {
				union(fathers, counts, num, num - 1);
			}
		}
		
		int longest = 0;
		for(int length : counts.values()) {
			longest = Math.max(longest, length);
		}
		return longest;
	}

	private void union(Map<Integer, Integer> fathers, Map<Integer, Integer> counts, int i, int j) {
		int fatherOfI = findFather(fathers, i);
		int fatherOfJ = findFather(fathers, j);
		if(fatherOfI != fatherOfJ) {
			fathers.put(fatherOfI, fatherOfJ);
			int countOfI = counts.get(i);
			int countOfJ = counts.get(j);
			counts.put(fatherOfJ, countOfI + countOfJ);
		}
	}
	
	private int findFather(Map<Integer, Integer> fathers, int i) {
		if(fathers.get(i) != i) {
			fathers.put(i, findFather(fathers, fathers.get(i)));
		}
		
		return fathers.get(i);
	}
	
}
